The size and complexity of state-of-the-art very large scale integrated circuits has made it necessary that much of their design and testing be computer-implemented.
Logic synthesis has now become an integral part of the synthesis pipeline of VLSI designs. Algorithms for automatic design of logic, targeting circuit area, delay, testability and power dissipation are now available in most logic synthesis systems. Analysis tools play an integral part in design automation, both in their own right as well as pat of synthesis systems where they are used to evaluate the quality of the synthesized circuits. Timing analysis analyzes the temporal behavior of a circuit; it determines when event occur in a circuit. In a synchronous digital system timing analysis is used to determine the delay of the combinational part of the circuit. The delay of the combinational part is the time taken for the outputs of the combinational circuit to settle to their final value after the inputs have been applied. This delay in turn determines the minimum permissible clocking period of the synchronous circuit. This invention addresses the problem of accurately determining the delay of combinational logic circuits. It is important to know this delay so that the clocking period can be made as short as feasible.
It is familiar practice in a CAD process to represent a combinational logic circuit as a Directed Acyclic Graph (DAG) with the nodes in the DAG corresponding to gates, and the links corresponding to the wires between the gates. Each DAG node can be weighted by the delay of the corresponding gate. The method used to arrive at the node weights is termed the delay model. Delay models vary in the level of accuracy with which they reflect the true gate delay. The choice of the delay model is largely orthogonal to the problem solved by this invention. Hence, the solutions provided by this invention are independent of the delay model used.
Until recently, circuit delay was computed as the length of the topologically longest path in a weighted-DAG representation of the circuit. While this approach is computationally very simple, it tends to be grossly inaccurate (pessimistic) in most situations. The source of this inaccuracy is that in most circuits, the designed signal value propagates to the circuit output via multiple paths, either by design or as a side effect of the application of logic synthesis and high-level synthesis algorithms. A path that is one of the topologically longest paths, but is never the first path to propagate a value to the output for any input vector, cannot be responsible for the circuit delay. Delay estimation under this additional complication requires a functional timing analysis of the circuit. Functional timing analysis is timing analysis which takes into account only true paths.
While various conditions have been proposed for characterizing a path actually responsible for circuit delay (also known as a true path), it was only recently that a correct necessary and sufficient condition was proposed. This was in a paper entitled "Delay Computation in Combinational Circuits: Theory and Algorithms", by Devadas, Keutzer and Malik, in the Proceedings of the International Conference on Computer-Aided Design (November 1991). The application of this condition, one path at a time, is not generally feasible because of the large number of long paths in a typical circuit. It was the extension of this condition in the paper to characterize sets of paths responsible for circuit delay that made its use practical. In that paper, a relationship was established between the truth or falsity of the set of longest paths and the testability of an appropriate multiple fault in the Equivalent Normal Form (ENF) representation of the circuit. The ENF of a circuit is a two-level representation that represents the logic function computed by the multi-level circuit while retaining path information. Since the ENF is exponentially larger than the multi-level representation this technique cannot directly be used in practice. To overcome this, it was then shown how test generation for the multiple fault could be performed on the original circuit by taking into consideration timing information during test generation. This approach was called timed test generation, and the associated calculus was called timed D-calculus.
There are some drawbacks associated with timed test generation:
In particular, Automatic Test Pattern Generators (ATPG) cannot be used directly for timed test generation. Considerable modification has to be performed to the basic routines like backward/forward implication and backtrace in the ATPG. The specifics of the modifications are intertwined into the details of the ATPG algorithm, and are therefore non-trivial.
Additionally, timing information of each error value at the input of the gate needs to be taken into account while evaluating a fanout edge of the gate. This adds considerable complexity to error value propagation.
Moreover, unlike in conventional stuck-fault test generation, when an error value has to be propagated across a gate, the evaluation of each fanout edge has to be performed separately. Since an error value may have to be propagated across a gate a large number of times, in timed test generation considerable additional computation is required over conventional test generation.
Finally, the extension of times test generation to handle complex gates is non-trivial.
The invention provides a technique which is relatively free of these problems.